

# 这题太巧妙了

from collections import defaultdict

class Solution:

    def subarraySum(self, nums, k):

        # n = len(nums)
        # # q = deque()
        # # q.append(nums[0])
        # # start = 1
        # # cnt = 0
        # # temp = nums[0]
        # # while q and  start < n:
        # #     if temp == k:

        # # nums.sort()
        # l, r = 0, 1
        # cnt = 0
        # temp = nums[0]
        # while r < n and l<n:
            
        #     if temp < k:
        #         temp += nums[r]
        #         r += 1
        #     elif temp > k:
        #         temp -= nums[l]
        #         l += 1
            
        #     else:
        #         cnt += 1
        #         # print(cnt)
        #         l += 1
        #         r += 1
        #         if r <= n - 1 or l <= n - 1:
        #             temp += (nums[r] - nums[l- 1])

        #     # print(l, r)
        #     # print(temp)
        #     if temp == k:
        #         cnt += 1
        # return cnt
        n = len(nums)
        s = [0] * (n + 1)
        for i, c in enumerate(nums):
            s[i + 1] = s[i] + c

        
        cnt = 0

        d = defaultdict(int)
        for c in s:
            # if k - c in d:
            cnt += d[c - k]

            d[c] += 1

        return cnt 







if __name__ == "__main__":
    nums = [1,2,1,2,1]
    # nums = [1,1,1]
    k = 3
    sol = Solution()
    ans = sol.subarraySum(nums, k)
    print(ans)
